# 反转每对括号间子串 https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/

class Solution:
    def reverseParentheses(self, s: str) -> str:
        # 长度
        n = len(s)
        # 栈
        stack = []
        # 结果字符串
        rst = ''
        i = 0 
        # 记录左括号个数，主要作用是 判断元素入栈，还是直接加入到 rst中
        count = 0
        while i < n:
            cur = s[i]

            # 1. 判断是否直接加入到 rst中
            if count == 0 and cur != "(":
                rst += cur
            # 2. 否则进栈：
            else:
                # 1. 是左括号入栈，count + 1
                if cur == "(" :
                    stack.append(cur)
                    count += 1
                # 2. 如果是右括号，那么 出栈一对括号的内容并且反转，出栈就是反转了（后进先出）
                elif cur == ")":
                    count -= 1
                    # 实现括号内字符反转
                    temp = ''
                    a = stack.pop()
                    while a != "(":
                        temp += a
                        a = stack.pop()
                    # 如果是最后一组括号，不需要入栈，直接加入到rst里面
                    if count == 0:
                        rst += temp
                        i += 1 # 注意 i 值加1
                        continue
                    # 再次入栈
                    for j in temp:
                        stack.append(j)                        
                # 3. 普通括号内的字符，入栈
                else:
                    stack.append(cur)
            i += 1

        return rst

# s = "(abcd)"
s = "a(bcdefghijkl(mno)p)q"

d = Solution()
c = d.reverseParentheses(s)
print(c)